⟸ Go Back ⟸

Exercise 8 (Homework 6).

(R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages))

Are they computable?

For each of the following functions f, find whether f is computable, \mathrm{Dom}(f)=\mathbb N (i.e. f is total), and what is \mathrm{Im}(f):

1. f(x)=\begin{cases} 1 &\text{if } \exists n\ M_n(x)\!\downarrow\\ \uparrow &\text{otherwise}\end{cases}
2. f(x)=\begin{cases} 1 &\text{if } \forall n\ M_n(x)\!\downarrow\\ \uparrow &\text{otherwise}\end{cases}
3. f(x)=\begin{cases} 1 &\text{if } \exists n\ M_x(n)\!\downarrow\\ \uparrow &\text{otherwise}\end{cases}
4. f(x)=\begin{cases} 1 &\text{if } \forall n\ M_x(n)\!\downarrow\\ \uparrow &\text{otherwise}\end{cases}